package leetcode_周赛._2023._03;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 336 场周赛
 * AC 2
 *
 * @author yezh
 * @date 2023/3/12 16:48
 */
public class _12 {

    /**
     * 重排数组以得到最大前缀分数
     * 算法: 前缀和
     */
    public int maxScore(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        long cur = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            cur += nums[i];
            if (cur > 0) ++ans;
        }
        return ans;
    }

    /**
     * 统计美丽子数组数目
     * 算法: 前缀和
     * 一个数组所有元素经过操作后, 元素为 0, 表示该数组中, 每个二进制位的 1 的总数为偶数个
     * 所以, 一个数组的所有元素异或为 0, 表示这个数组就是美丽数组
     * 使用前缀和算出前 i 个元素的异或
     * 前缀和中有多少对不同下标的相同元素对, 就有多少个数组
     */
    public long beautifulSubarrays(int[] nums) {
        int n = nums.length, cur = 0;
        long ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        // 如果碰到 cur = 0, 表示 [0, i] 是一个美丽数组, 所以需要这一步
        // 或者说, 使用前缀和的话, prefix[0] = 0, 现在不用数组表示, 但这个 0 不能丢
        cnt.put(0, 1);
        for (int i = 0; i < n; i++) {
            cur ^= nums[i];
            int c = cnt.getOrDefault(cur, 0);
            ans += c;
            cnt.put(cur, c + 1);
        }
        return ans;
    }

}
